The present invention relates to detection of errors introduced in data while being transmitted over a communications networks, and more particularly to an efficient implementation of a cyclic redundancy check (CRC) generator for high speed communication networks such as SONET.
Demand for high performance communication networks capable of transporting multiple types of data, such as text, audio and video data, is on the rise. To carry greater amount of data over existing communication channels, such as fiber-optic communication channels, network carriers are increasingly using high bandwidth technologies, such as wave division multiplexing (WDM) and optical carrier (OC) level 48. Such communication networks rely upon high-performance packet switches, such as asynchronous transfer mode (ATM) switches, frame relay switches and internet protocol (IP) routers which route the incoming packets to their desired destinations.
Inherent in most digital communication channels are errors introduced when transferring frames, packets or cells containing data. Such errors are often caused by electrical interference or thermal noise. Data transmission error rates depend, in part, on the medium which carries the data. Typical bit error rates for copper based data transmission systems are in the order of 10−6. Optical fibers have typical bit error rates of 10−9 or less. Wireless transmission systems, on the other hand, may have error rates of 10−3 or higher. To maintain data integrity during transmission, most communication systems deploy an error-control mechanism.
A known technique for error control, commonly referred to as error detection, involves detection of errors by the receiver followed by a retransmission of the data by the transmitter. In accordance with this error detection technique, a code is computed from the data at the transmitting end using a predefined algorithm. The data and the code—which is appended to the data—are subsequently transmitted to the receiver. The receiver, using the same predefined algorithm, computes another code from the transmitted data. If the code computed by the receiver matches the code computed by the transmitter, the data is considered to be free of errors.
Many of the conventional algorithms use polynomial codes to generate error-detecting codes. An error-detecting code generated using a polynomial code is commonly referred to as a cyclic redundancy check (CRC). A polynomial code is typically specified by its generator polynomial g(x) which is used by both the transmitter and the receiver to compute their respective CRCs. A CRC is the remainder of the division of data by a generator polynomial. The number of bits in the remainder is the same as the degree of the generator polynomial. If the CRC computed from the data by the transmitter does not match the CRC computed from the data received by the receiver, the data is flagged as corrupt, thus forcing the transmitter to retransmit the data.
There are several well-known generator polynomials. For example, generator polynomial g(x)=x8+x2+x+1 is used to generate CRC-8 (i.e., an 8-bit CRC) to detect ATM header errors. Similarly the following well known generator polynomial:g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1  (1)
is used to generate a 32-bit CRC when transmitting data in conformity with, for example, CCIT V.42 modem standard or IEEE 802 LAN standards. CRC computation is typically carried out in the data link layer of a network by either software, hardware or a combination of hardware and software. A logic hardware dedicated to computation of CRC often includes a number of shift registers and modulo 2 adders/subtractors (XORs).
FIG. 1 shows a prior art logic hardware 10 that is adapted to compute a CRC-5 using the generator polynomial g(x)=x5+x4+x2+1. Logic hardware 10 includes five shift registers 12, 14, 16, 18, 20 and three 2-input XOR gates 22, 24, 26. With every transition of the clock, one bit of data is serially applied to input terminal IN1 of XOR gate 22, with the most significant bit of the data applied first. Furthermore, with every transition of the clock, each of the shift registers 12, 14, 16, 18, 20 shifts the data present at its respective D terminal to its respective output terminal Q (i.e., to. the left). The data present at output terminals Q of shift registers 12, 14, 16, 18, 20 form the 5 bits of the CRC-5.
A commonly known standard referred to as synchronous optical network (SONET) defines a synchronous frame structure for transmitting signals using time division multiplexed (TDM) technique. In accordance with the TDM technique, data bits associated with different channels are interleaved in the time domain to form a composite bit stream. For example, assume that each time slot is about 15 us for a single voice channel operating at 64 Kb/sec. Accordingly, five such channels may be multiplexed via the TDM technique if the bit streams of successive channels are delayed by 3 usec.
The basic building block of an exemplary SONET has a bit rate of 51.84 Mb/s which has a corresponding optical signal referred to as OC-1. Bits disposed in packets transported over the SONET channel (Packet over SONET), are carried over a bus having a width of, e.g. 16 bits. The 16-bit data are subsequently aggregated by an integrated circuit, such as a SONET framer, adapted to carry the data using a wider, e.g. 128-bit (i.e., 16-byte) bus. To generate a CRC-32 for a packet whose bytes are received over a 128-bit bus using conventional approach would require a relatively large number of shift registers and XOR gates. As the number of shift registers and XOR gates increases, it becomes more difficult to generate the CRC-32 within the time period set by the operating clock frequency.
There is a need for efficient implementation of logic hardware adapted to timely generate CRCs employing polynomials of higher degrees.